1. Field of the Invention
The current invention relates to a method of bite rate estimation in data or video compression, and in particular, but not exclusively, to a method of bit rate estimation for rate distortion (RD) optimization. The invention also relates variable length coding (VLC) and more particular to context-based variable length coding (CAVLC) and to Advanced Video Coding (AVC), also known as MPEG4-part 10 and H.264.
2. Background Information
The Motion Picture Experts Group (MPEG) is responsible for the MPEG series of data compression technologies, i.e. MPEG1, MPEG2 and MPEG4, which gave rise to MP3, VCDs and DVDs and revolutionized audio and visual distribution. Separately, the ITU-T Video Coding Experts Group (VCEG) developed the ITU-T H.263 standard for video compression that is widely used in videoconferencing systems. However, the appearance and development of various new multimedia services such as internet-based video applications gave rise to the need for even higher coding efficiency and in 2001 the two groups formed a Joint Video Team (JVT) to develop a new “international” standard for low bit rate visual communications. The result is the Advanced Video Coding (AVC) standard, which is actually two jointly maintained and identical standards MPEG4 Part 10 (ISO/IEC 14496-10) and ITU-T H.264. The entire contacts of the AVC standards, i.e. MPEG4 Part 10 and ITU-T H.264, are incorporated herein by reference. Further information on the Standard can also be found in “H.264 and MPEG-4 Video Compression—video coding for next generation multimedia” by Iain E. G. Richardson and published by John Wily & Sons in 2003 (ISBN: 978-0-470-84837-1).
Like earlier MPEG standards AVC does not define an encoder or decoder, but defines the syntax of an encoded video bitstream together with a method of decoding the bitstream, however a typical AVC compliant encoder may look that illustrated in FIG. 1. This encoder has four basic functional elements of prediction, transform, quantization and entropy encoding in common with other MPEG standards, but the details of each functional element has changed. New and advanced techniques are introduced in the AVC standard include intra prediction for 1-frame encoding, multi-frames inter prediction, small block-size transform coding, context-adaptive arithmetic entropy coding, de-blocking filtering, flexible macroblock ordering (FMO) and arbitrary slice ordering (ASO), etc. These advanced techniques provide good video quality at substantially lower bit rates than previous standards, and in particular up to 50% lower bit rate than MPEG-2, H.263, or MPEG-4 Part 2.
The following is a brief description of AVC encoding with reference to FIG. 1. The skilled addressee should be knowledgeable in video compression and in particular video compression using the AVC standard.
The encoder processes a current frame in sub-frame units called macroblocks, which correspond to a 16×16 pixel block of the frame (AVC also allows a frame to be divided into up to 8 slice groups, which comprises a sequence of macroblocks, and which may also be divided into a series of individual slices). For each processed macroblock the encoder forms a prediction macroblock, which is either based on a previously coded and reconstructed macroblock from within the current frame, known as intra prediction, or on a previous frame that has already been coded, known as inter prediction. The encoder subtracts the prediction macroblock from the current macroblock to produce a difference macroblock. The difference macroblock is transformed using a block transform and quantized to give a set of quantized transform coefficients. The transform coefficients are combined with other information required to decode the macroblock, such as the prediction mode used, the quantizer step size, motion vector information etc and the all the information is then compressed using an entropy encoding technique such as CAVLC to form a compressed bitstream which can transmitted over a network or stored for future retrieval.
To enable more accurate prediction, and hence more efficient and better quality compression, AVC provides more flexible prediction methods than previous ITU or MPEG standards. Intra prediction can use 4×4, 8×8 or 16×16 block sizes to predict a macroblock from a previously coded block within the same frame: There are a total of 9 prediction modes available for a 4×4 block, and 4 prediction modes available for each of a 8×3 and 16×16 block. Inter prediction uses a tree structured motion compensation which provides four different block sizes 16×6 16×8, 8×16, 8×8, each of which can be further sub-partitioned in 8×8, 8×4, 4×8 or 4×4 blocks giving rise to a large number of possible block combinations within each macroblock.
To achieve the highest coding efficiency AVC also uses a rate-distortion (RD) optimization technique to get the best coding result in terms of maximizing coding quality and minimizing bit rates. This means that the encoder has to code each macroblock by exhaustively trying all the mode combinations including the different intra and inter prediction modes and all entropy coding techniques. When a macroblock is in an I-slice it can be coded using intra prediction meaning the RD algorithm must search the 17 Intra prediction modes. When a macroblock is in a P-slice it can be coded using either Intra prediction or Inter prediction and must search all Intra and Inter prediction modes. Therefore, the complexity and computation load of video coding in AVC increase drastically compared to any previous standards.